A number of techniques have been conceived, some of which have been used, for speeding computations by computers. To date, the principal approaches to speeding up computers used have been to simply enhance the processing speed capability of traditional von Neumann architecture computers, the provision of a few coordinated computers operating in parallel, and vector processors. Speed up techniques include locality of reference, provided by such means as cache memory, local storage and specialized networks. These all provide relatively small speed ups. Improved instruction sets can also provide a degree of speed up.
Considerably greater speed ups may be achieved by exploiting concurrency through the use of parallel structures such as multiple functional units in each processor, pipelines, vector processors, and multiprocessors. For example, Bolt, Beranek and Newman, Inc.'s Butterfly, which uses thousands of processors, and the Thinking Machine Company's Connection Machine, a single instruction multiple datastream (SIMD) array machine with as many as 64,000 processors, may achieve very substantial speed ups for some types of problems suitable to their architecture.
In my earlier patents, Sullivan et al. U.S. Pat. Nos. 4,484,262 and 4,707,781, the disclosure of which is incorporated herein by reference, we have shown how the randomization or pseudo randomization (hashing) of data among numerous memory units and conflict-reduction means in accessing memory units can speed up parallel digital computers.